Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode buildTree(int[] inorder, int[] postorder) {
  12.     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  14.     for (int i = 0; i < inorder.length; i++) {
  15.       map.put(inorder[i], i);
  16.     }
  18.     return build(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1, map);
  19.   }
  21.   TreeNode build(int[] post, int i1, int j1, int[] in, int i2, int j2, Map<Integer, Integer> map) {
  22.     if (i1 > j1 || i2 > j2) {
  23.       return null;
  24.     }
  26.     TreeNode root = new TreeNode(post[j1]);
  28.     int index = map.get(root.val);
  29.     int left = index - i2;
  31.     root.left = build(post, i1, i1 + left - 1, in, i2, index - 1, map);
  32.     root.right = build(post, i1 + left, j1 - 1, in, index + 1, j2, map);
  34.     return root;
  35.   }
  36. }